package com.fujica.db_operation.entity;

/**
 * @ClassName sortSearchTree
 * @Description TODO 二叉排序树/平衡二叉树
 * @Author admin
 * @Date 2020/7/3 14:12
 * @Version 1.0
 **/
public class SortSearchTree {

    // 定义根节点
    private TreeNode root;
    // 定义二叉树的长度
    private long size;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public long getSize() {
        return size;
    }

    /**
     * 往树中加节点
     * @param data
     * @return
     */
    public Boolean addTreeNode(Integer data) {

        if (root == null) {
            root = new TreeNode(data);
            System.out.println("数据成功插入到平衡二叉树中！");
            return true;
        }
        // 即将被插入的节点
        TreeNode insertNode = new TreeNode(data);
        // 保存当前节点
        TreeNode currentNode = root;
        // 保存父节点
        TreeNode parentNode;
        // 循环比较节点
        while(true) {

            // 赋值当前节点
            parentNode =  currentNode;

            // 第一种情况 当前节点 > 新插入的值
            if (currentNode.getData() > data) {
                currentNode = currentNode.getLeft();
                // 当前节点的左子树为空的情况
                if (currentNode == null) {
                    parentNode.setLeft(insertNode);
                    System.out.println("数据成功插入到平衡二叉树中！");
                    size++;
                    return true;
                }
            }else if (currentNode.getData() < data) {
                // 第二种情况 当前节点 < 新插入的值
                currentNode = currentNode.getRight();
                // 当前节点的父节点的右子节点为空
                if (currentNode == null) {
                    parentNode.setRight(insertNode);
                    System.out.println("数据成功插入到平衡二叉树中！");
                    size++;
                    return true;
                }
            }else {
                System.out.println("输入的数据与节点相同！");
                return false;
            }
        }
    }

    public TreeNode findTreeNode(Integer data) {

        TreeNode current = root;

        while (current != null) {
            if (current.getData() > data) {
                current = current.getLeft();
            }else if (current.getData() < data) {
                current = current.getRight();
            }else {
                return current;
            }
        }
        return null;
    }

}
